package org.spp.voronoi;

import java.util.ArrayList;
import java.util.List;
import org.apache.commons.math.util.MathUtils;

/**
 * Cell.java
 * @author Ilio Catallo, Eleonora Ciceri
 * @version 1.0
 * 
 * Description: the class implements the cell of the voronoi diagram
 * 
 * Date: Jul 10, 2011
 */
public abstract class Cell {
    
    // Attributes
    protected VoronoiDiagram voronoiDiagram;
    private int id;
    protected Centroid centroid;
    protected List<Facet> facets;
    protected List<Vertex> vertexes;
    
   /**
     * Constructor for the class Cell
     * @param centroid
     * @param voronoiDiagram 
     */
    public Cell(Centroid centroid, VoronoiDiagram voronoiDiagram) {
        this.centroid = centroid;
        this.voronoiDiagram = voronoiDiagram;
        
        this.facets = new ArrayList<Facet>();
        this.vertexes = new ArrayList<Vertex>();
        this.id = 0;
        
        this.centroid.setCell(this);
    }
    
    /**
     * Constructor for the cell
     * @param centroid
     * @param id
     * @param voronoiDiagram 
     */
    public Cell(Centroid centroid, int id, VoronoiDiagram voronoiDiagram) {
        this (centroid, voronoiDiagram);
        this.id = id;
    }
    
    /**
     * Method that returns the Id of the cell
     * @return id
     */
    public int getId() {
        return id;
    }
    
    /**
     * Method that returns the centroid of the cell
     * @return centroid
     */
    public Centroid getCentroid() {
        return centroid;
    }
    
    /**
     * Method that returns the facets that are associated with the cell
     * @return facets
     */
    public List<Facet> getFacets() {
        return facets;
    }
    
    /**
     * Method that returns all the vertexes that are associated with the cell
     * @return vertexes
     */
    public List<Vertex> getVertexes() {
        return vertexes;
    }
    
    /**
     * Method that adds a facet to the list of the cell facets
     * @param facet 
     */
    public void addFacet(Facet facet) {
        facets.add(facet);
    }
    
    /**
     * Method that generate the cell, computing its facets and vertexes
     */
    public void generate(){        
        computeFacets();
        computeVertexes();
        removeBoundedRegionFacets();        
    }
    
    /**
     * Method for the computation of the edges of the current cell
     */
    public void computeEdges() {        
        for (int i = 0; i < vertexes.size(); i++)
            vertexes.get(i).computeEdges();
    }
    
    public List<Facet> findVertexFacets(Vertex vertex){
        //Variables
        List<Facet> vertexFacets = new ArrayList<Facet>();
        double[] vertexCoordinates = vertex.getCoordinates();   
        
        // Compute the linear system that describes the cell
        Jama.Matrix[] linearSystem = computeLinearSystem();
        Jama.Matrix A = linearSystem[0];
        Jama.Matrix b = linearSystem[1];
     
        // Find the planes
        Jama.Matrix result = A.times(new Jama.Matrix(vertexCoordinates, vertexCoordinates.length)).minus(b);
        
        for (int i = 0; i < facets.size(); i++)            
            if (Math.abs(result.get(i,0)) < MathUtils.EPSILON)
                vertexFacets.add(facets.get(i));
        
        return vertexFacets;
    }     
    
    /**
     * Method that calculates the facets of the cell
     */
    private void computeFacets() {
        // Variables
        List<Centroid> adjCentroids = centroid.getAdjCentroids();
        List<Facet> newFacets = new ArrayList<Facet>();
        newFacets.addAll(voronoiDiagram.getBoundedRegionFacets());
        
        // A-priori the cell is made of all the facets of the bounded region
        for(int i=0; i < newFacets.size(); i++)
            newFacets.get(i).addCell(this, 1);        
        
        // Check if already exists a facet created by adj cells, otherwise it creates them from scratch
        for (int i = 0; i < adjCentroids.size(); i++){            
            Cell adjCell = adjCentroids.get(i).getCell();
            Facet oldFacet = isFacetInAdjCell(adjCell);
            
            // If old Cell is != null it means that it is already present in the facets list
            if (oldFacet == null) {
                Facet newFacet = createNewFacet(centroid, adjCentroids.get(i));
                newFacets.add(newFacet);
                adjCell.addFacet(newFacet);
            }             
        }
        
        // In this way we keep the bounded region facets as the first six facets in the list
        newFacets.addAll(facets);
        facets = newFacets;
    } 
    
    /**
     * Method that calculates the vertexes of a specific cell
     */
    private void computeVertexes() {
        // Compute the linear system
        Jama.Matrix[] linearSystem = computeLinearSystem();
        Jama.Matrix A = linearSystem[0];
        Jama.Matrix b = linearSystem[1];
        
        // Vertex enumeration
        vertexes = vertexEnumeration(A, b);
    }
    
    /**
     * Method that creates the linear system that describes the cell
     * @return linearSystem
     */
    private Jama.Matrix[] computeLinearSystem(){
        //Variables
        int dimension = facets.get(0).getCoefficients().length;
        Jama.Matrix A = new Jama.Matrix(facets.size(), dimension - 1);
        Jama.Matrix b = new Jama.Matrix(facets.size(), 1);
        
        Jama.Matrix[] linearSystem = new Jama.Matrix[2];
        
        // Build the coefficient matrix 
        for (int i = 0; i < facets.size(); i++){            
            double[] coefficients = facets.get(i).getCoefficients();
            int sign = facets.get(i).getSign(this);
      
            for(int j = 0; j < (dimension - 1); j++)
                A.set(i,j, sign*coefficients[j]);
            
            b.set(i,0, sign*coefficients[dimension - 1]);            
        }
        
        linearSystem[0] = A;
        linearSystem[1] = b;
        
        return linearSystem;        
    }   
    
    /**
     * Method that checks if a vertex is already present in another adjacent cell
     * @param vertex
     * @return vertex
     */
    protected Vertex isVertexInAdjCells(Vertex vertex){
        // Variables
        List<Cell> adjCells = centroid.getAdjCells();
     
        for (int i = 0; i < adjCells.size(); i++){            
            List<Vertex> adjCellVertexes = adjCells.get(i).getVertexes();
            
            for (int j = 0; j < adjCellVertexes.size(); j++)                
                if (adjCellVertexes.get(j).isEqual(vertex))
                    return adjCellVertexes.get(j); 
        }
        
        return null;
    }
    
    /**
     * Method that check if a facet is already present in another adhacent cell
     * @param adjCell
     * @return facet
     */
    private Facet isFacetInAdjCell(Cell adjCell){
        // Variables
        List<Facet> adjCellFacets = adjCell.getFacets();
        
        for (int i = 0; i < adjCellFacets.size(); i++)
            if (adjCellFacets.get(i).isFacetInCell(this) && !adjCellFacets.get(i).isInBoundedRegion())
                return adjCellFacets.get(i);         // The plane already exists        
        
        return null;        
    }    
    
    /**
     * Method that checks if a given vertex belongs to the cell or if it is outside.
     * @param A
     * @param b
     * @param vertex
     * @return isOutside
     */
    protected boolean isOutside(Jama.Matrix A, Jama.Matrix b, Jama.Matrix vertex){        
        // Check if respect the system (inside the convex hull)
        Jama.Matrix result = A.times(vertex).minus(b);
        
        for (int i = 0; i < facets.size();i++)            
            if (result.get(i, 0) > MathUtils.EPSILON)
                return true;
        
        return false;
    }
    
    /**
     * After the vertex enumeration we can check which facets of the bounded
     * region are shared with the cell, and remove the others from the list
     * of the cell facets
     */
    protected abstract void removeBoundedRegionFacets();
    
    /**
     * Method that performs the vertex enumeration starting from the facets of the cell
     * @param A
     * @param b
     * @return vertexes
     */
    protected  abstract List<Vertex> vertexEnumeration(Jama.Matrix A, Jama.Matrix b);    
    
    /**
     * Method for the creation of a new facet inside the cell
     * @param firstCentroid
     * @param secondCentroid
     * @return newFacet
     */
    protected abstract Facet createNewFacet(Centroid firstCentroid, Centroid secondCentroid);    
    
}
